#include "sort.h"
#include <time.h>
int cmp(void const* e1, void const* e2) {
	return *(int*)e1 - *(int*)e2;
}
void test() {
	int t0 = clock();
	srand((unsigned int)time(NULL));
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	int* a9 = (int*)malloc(sizeof(int) * N);
	if (a1== NULL) {
		perror("a1 malloc fail");
		exit(-1);
	}if (a2 == NULL) {
		perror("a2 malloc fail");
		exit(-1);
	}if (a3 == NULL) {
		perror("a3 malloc fail");
		exit(-1);
	}if (a4 == NULL) {
		perror("a4 malloc fail");
		exit(-1);
	}
	for (int i = 0; i < N; i++) {
		a1[i] = rand();
		int z = rand();
		//a1[i] = a1[i] * z % 1000000007; 
		a1[i] = a1[i] * z % N; 
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
		a9[i] = a1[i];
		}
	printf("N = %d\n", N);

	/*int begin1=clock();
	InsertSort(a1, N);
	int end1 = clock();
	printf("InsertSort Time=%d ms\n", end1 - begin1);*/

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	printf("ShellSort Time=%d ms\n", end2 - begin2);
	
	/*int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	printf("SelectSort Time=%d ms\n", end3 - begin3);*/

	/*int begin4 = clock();
	BubbleSort(a4, N);
	int end4 = clock();
	printf("BubbleSort Time=%d ms\n", end4 - begin4);*/
	
	int begin5 = clock();
	//QuickSortNonR(a2, 0, N - 1);
	QuickSort(a5, 0,N-1);
	//qsort(a2, N, 4, cmp);
	int end5 = clock();
	printf("QuickSort Time=%d ms\n", end5-begin5);
	//printf("qSort Time=%d ms\n", end5 - begin5);

	int begin6 = clock();
	HeapSort(a6, N);
	int end6 = clock();
	printf("HeapSort Time=%d ms\n", end6 - begin6);

	int begin7 = clock();
	MergeSortNonR(a7, N);
	int end7 = clock();
	printf("MergeSort Time=%d ms\n", end7 - begin7);

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = clock();
	printf("CountSort Time=%d ms\n", end8 - begin8);

	int begin9 = clock();
	RedixSort(a9, N);
	int end9 = clock();
	printf("RedixSort Time=%d ms\n", end9 - begin9);
	//free(a9);
	//a5 = NULL;

	printf("\n");
	//int arr[10]={ 2673,231,312,7,872,871,987,8,1,0 };
	//int arr[20] = { 6,1,2,7,9,3,4,5,10,8,18,20,19,17,16,15,14,13,12,11};
	int arr[20] = { 6,1,2,7,9,3,4,5,10,8,18,20,19,17,16,15,14,13,12,11 };

	for(int i = 0; i < 20; i++)printf("%d ",arr[i]);
	//MergeSortNonR(arr, 20);
	//CountSort(arr, 20);
	//QuickSortNonR(arr, 0, 19);
	//QuickSort(arr, 0 , 19);
	//HeapSort(arr, 10);
	RedixSort(arr, 20);
	printf("\n");
	for (int i = 0; i < 20; i++)printf("%d ", arr[i]);
}
int main(){

	test();
	return 0;
}